/************************************************************************/
//GZIP压缩
/************************************************************************/
#include "GZip.h"

#include "Tools.h"
// INCLUDES

#define FTEXT_MASK		1
#define FHCRC_MASK		2
#define FEXTRA_MASK		4
#define FNAME_MASK		8
#define FCOMMENT_MASK	16
// Tipos de bloques.
#define BTYPE_NONE		0
#define BTYPE_FIXED		1
#define BTYPE_DYNAMIC	2
#define BTYPE_RESERVED	3
// Lites.
#define MAX_BITS			16
#define MAX_CODE_LITERALS	287
#define MAX_CODE_DISTANCES	31
#define MAX_CODE_LENGTHS	18
#define EOB_CODE			256
// Datos prefijados (LENGTH: 257..287 / DISTANCE: 0..29 / DYNAMIC_LENGTH_ORDER: 0..18).

int readBits(char gzip[],int n, int *gzipBit, int *gzipByte, int *gzipIndex);
int readCode(char gzip[],int tree[], int *gzipBit, int *gzipByte, int *gzipIndex);
void decodeCodeLengths(char gzip[],int lengthTree[],int count, char* aDesData, int *gzipBit, int *gzipByte, int *gzipIndex);
void createHuffmanTree(char bits[],int aLen,int maxCode, int aDesData[]);


void GZIP_inflate(char* gzip, int aLen,char* aDesData)
{
	int LENGTH_EXTRA_BITS[] = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0,99,99};
	int LENGTH_VALUES[]       = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258,0,0};
	int DISTANCE_EXTRA_BITS[]  = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
	int DISTANCE_VALUES[]       = {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577};
	int DYNAMIC_LENGTH_ORDER[]  = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
	int gzipIndex,gzipByte,gzipBit;
	// Inicializa.
	int *literalTree,*distanceTree, *lengthTree;
	char *iteralBits, *distanceBits;
	
	literalTree = distanceTree = lengthTree = NULL;
	iteralBits = distanceBits = NULL;
	gzipIndex=gzipByte=gzipBit=0;
	// Cabecera.
	if (readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex)!=0x8B1F||readBits(gzip,8, &gzipBit, &gzipByte, &gzipIndex)!=8)
		return;
	// Flag.
	int flg=readBits(gzip,8, &gzipBit, &gzipByte, &gzipIndex);
	// Fecha(4) / XFL(1) / OS(1).
	gzipIndex+=6;
	// Comprueba los flags.
	if ((flg&FEXTRA_MASK)!=0) gzipIndex+=readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex);
	if ((flg&FNAME_MASK)!=0) while (gzip[gzipIndex++]!=0);
	if ((flg&FCOMMENT_MASK)!=0) while (gzip[gzipIndex++]!=0);
	if ((flg&FHCRC_MASK)!=0) gzipIndex+=2;
	// Tama de los datos descomprimidos.
	int index=gzipIndex;
	gzipIndex=aLen-4;
	int uncompressedIndex=0;
	gzipIndex=index;
	// Bloque con datos comprimidos.
	int bfinal=0,btype=0;
	do
	{
		// Lee la cabecera del bloque.
		bfinal=readBits(gzip,1, &gzipBit, &gzipByte, &gzipIndex);
		btype=readBits(gzip,2, &gzipBit, &gzipByte, &gzipIndex);
		// Comprueba el tipo de compresi.
		if (btype==BTYPE_NONE)
		{
			// Ignora los bits dentro del byte actual.
			gzipBit=0;
			// LEN.
			int len=readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex);
			// NLEN.
			//int nlen=readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex);
            readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex);
			// Lee los datos.
			memcpy(aDesData+uncompressedIndex,gzip+gzipIndex,len);
			gzipIndex+=len;
			// Actualiza el dice de los datos descomprimidos.
			uncompressedIndex+=len;
		}
		else
		{
			if (btype==BTYPE_DYNAMIC)
			{
				// Nero de datos de cada tipo.
				int hlit=readBits(gzip,5, &gzipBit, &gzipByte, &gzipIndex)+257;
				int hdist=readBits(gzip,5, &gzipBit, &gzipByte, &gzipIndex)+1;
				int hclen=readBits(gzip,4, &gzipBit, &gzipByte, &gzipIndex)+4;
				// Lee el nero de bits para cada cigo de longitud.
				char *lengthBits=(char*) Tools_Malloc(MAX_CODE_LENGTHS+1);
				memset(lengthBits,0,MAX_CODE_LENGTHS+1);
				for (int i=0;i<hclen;i++) lengthBits[DYNAMIC_LENGTH_ORDER[i]]=(char)readBits(gzip,3, &gzipBit, &gzipByte, &gzipIndex);
				// Crea los cigos para la longitud.
				lengthTree=(int*) Tools_Malloc(((MAX_CODE_LENGTHS<<1)+MAX_BITS)*sizeof(int));
				memset(lengthTree,0,((MAX_CODE_LENGTHS<<1)+MAX_BITS)*sizeof(int));
				createHuffmanTree(lengthBits,MAX_CODE_LENGTHS+1,MAX_CODE_LENGTHS,lengthTree);
				// Genera los boles.
				iteralBits=(char*) Tools_Malloc(hlit);
				memset(iteralBits,0,hlit);
				decodeCodeLengths(gzip,lengthTree,hlit,iteralBits, &gzipBit, &gzipByte, &gzipIndex);
				literalTree=(int*) Tools_Malloc((((hlit-1)<<1)+MAX_BITS)*sizeof(int));
				memset(literalTree,0,(((hlit-1)<<1)+MAX_BITS)*sizeof(int));
				createHuffmanTree(iteralBits,hlit,hlit-1,literalTree);
				
				distanceBits=(char*) Tools_Malloc(hdist);
				memset(distanceBits,0,hdist);
				decodeCodeLengths(gzip,lengthTree,hdist,distanceBits, &gzipBit, &gzipByte, &gzipIndex);
				distanceTree=(int*) Tools_Malloc((((hdist-1)<<1)+MAX_BITS)*sizeof(int));
				memset(distanceTree,0,(((hdist-1)<<1)+MAX_BITS)*sizeof(int));
				createHuffmanTree(distanceBits,hdist,hdist-1,distanceTree);
				Tools_Free((void**)&lengthBits);
			}
			else
			{
				char *literalBits=(char*) Tools_Malloc(MAX_CODE_LITERALS+1);
				memset(literalBits,0,MAX_CODE_LITERALS+1);
				int i = 0;
				for (i=0;i<144;i++) literalBits[i]=8;
				for (i=144;i<256;i++) literalBits[i]=9;
				for (i=256;i<280;i++) literalBits[i]=7;
				for (i=280;i<288;i++) literalBits[i]=8;
				
				literalTree=(int*) Tools_Malloc(((MAX_CODE_LITERALS<<1)+MAX_BITS)*sizeof(int));
				memset(literalTree,0,((MAX_CODE_LITERALS<<1)+MAX_BITS)*sizeof(int));
				createHuffmanTree(literalBits,MAX_CODE_LITERALS+1,MAX_CODE_LITERALS,literalTree);
				//
				distanceBits=(char*) Tools_Malloc(MAX_CODE_DISTANCES+1);
				memset(distanceBits,0,MAX_CODE_DISTANCES+1);
				for (i=0;i<MAX_CODE_DISTANCES+1;i++) distanceBits[i]=5;
				distanceTree=(int*) Tools_Malloc(((MAX_CODE_DISTANCES<<1)+MAX_BITS)*sizeof(int));
				memset(distanceTree,0,((MAX_CODE_DISTANCES<<1)+MAX_BITS)*sizeof(int));
				createHuffmanTree(distanceBits,MAX_CODE_DISTANCES+1,MAX_CODE_DISTANCES,distanceTree);
				Tools_Free((void**)&literalBits);
			}
			// Descomprime el bloque.
			int code=0,leb=0,deb=0;
			while ((code=readCode(gzip,literalTree, &gzipBit, &gzipByte, &gzipIndex))!=EOB_CODE)
			{
				if (code>EOB_CODE)
				{
					code-=257;
					int length=LENGTH_VALUES[code];
					if ((leb=LENGTH_EXTRA_BITS[code])>0) length+=readBits(gzip,leb, &gzipBit, &gzipByte, &gzipIndex);
					code=readCode(gzip,distanceTree, &gzipBit, &gzipByte, &gzipIndex);
					int distance=DISTANCE_VALUES[code];
					if ((deb=DISTANCE_EXTRA_BITS[code])>0) distance+=readBits(gzip,deb, &gzipBit, &gzipByte, &gzipIndex);
					// Repite la informaci.
					int offset=uncompressedIndex-distance;
					while (distance<length)
					{
						memcpy(aDesData+uncompressedIndex,aDesData+offset,distance);
						uncompressedIndex+=distance;
						length-=distance;
						distance<<=1;
					}
					//		System.arraycopy(uncompressed,offset,uncompressed,uncompressedIndex,length);
					memcpy(aDesData+uncompressedIndex,aDesData+offset,length);
					uncompressedIndex+=length;
				}
				else aDesData[uncompressedIndex++]=(char)code;
			}
		}
		Tools_Free((void**)&literalTree);
		Tools_Free((void**)&distanceTree);
		Tools_Free((void**)&lengthTree);
		Tools_Free((void**)&iteralBits);
		Tools_Free((void**)&distanceBits);
	}
	while (bfinal==0);
	//
	return;
}

void decodeCodeLengths(char gzip[],int lengthTree[],int count, char* aDesData, int *gzipBit, int *gzipByte, int *gzipIndex)
{
	char *bits=(char*) Tools_Malloc(count);
	memset(bits,0,count);
	for (int i=0,code=0,last=0;i<count;)
	{
		code=readCode(gzip,lengthTree, gzipBit, gzipByte, gzipIndex);
		if (code>=16)
		{
			int repeat=0;
			if (code==16)
			{
				repeat=3+readBits(gzip,2, gzipBit, gzipByte, gzipIndex);
				code=last;
			}
			else
			{
				if (code==17) repeat=3+readBits(gzip,3, gzipBit, gzipByte, gzipIndex);
				else repeat=11+readBits(gzip,7, gzipBit, gzipByte, gzipIndex);
				code=0;
			}
			while (repeat-->0) bits[i++]=(char)code;
		}
		else bits[i++]=(char)code;
		//
		last=code;
	}
	memcpy(aDesData,bits,count);
	Tools_Free((void**)&bits);
	return;
}

int readBits(char gzip[],int n, int *gzipBit, int *gzipByte, int *gzipIndex)
{
	// Asegura que tenemos un byte.
	int data=((*gzipBit)==0?((*gzipByte)=(gzip[(*gzipIndex)++]&0xFF)):((*gzipByte)>>(*gzipBit)));
	// Lee hasta completar los bits.
	for (int i=(8-(*gzipBit));i<n;i+=8)
	{
		(*gzipByte)=(gzip[(*gzipIndex)++]&0xFF);
		data|=((*gzipByte)<<i);
	}
	// Ajusta la posici actual.
	(*gzipBit)=((*gzipBit)+n)&7;
	// Devuelve el dato.
	return (data&((1<<n)-1));
}

int readCode(char gzip[],int tree[], int *gzipBit, int *gzipByte, int *gzipIndex)
{
	int node=tree[0];
	while (node>=0)
	{
		// Lee un byte si es necesario.
		if ((*gzipBit)==0) (*gzipByte)=(gzip[(*gzipIndex)++]&0xFF);
		// Accede al nodo correspondiente.
		node=((((*gzipByte)&(1<<(*gzipBit)))==0)?tree[node>>16]:tree[node&0xFFFF]);
		// Ajusta la posici actual.
		(*gzipBit)=((*gzipBit)+1)&7;
	}
	return (node&0xFFFF);
}

void createHuffmanTree(char bits[],int aLen,int maxCode, int aDesData[])
{
	// Nero de cigos por cada longitud de cigo.
	int *bl_count=(int*) Tools_Malloc((MAX_BITS+1)*sizeof(int));
	memset(bl_count,0,(MAX_BITS+1)*sizeof(int));
	int i = 0;
	for (i=0;i<aLen;i++) bl_count[bits[i]]++;
	// Mimo valor numico del cigo para cada longitud de cigo.
	int code=0;
	bl_count[0]=0;
	int *next_code=(int*) Tools_Malloc((MAX_BITS+1)*sizeof(int));
	memset(next_code,0,(MAX_BITS+1)*sizeof(int));
	for (i=1;i<=MAX_BITS;i++) next_code[i]=code=(code+bl_count[i-1])<<1;
	// Genera el bol.
	// Bit 31 => Nodo (0) o cigo (1).
	// (Nodo) bit 16..30 => dice del nodo de la izquierda (0 si no tiene).
	// (Nodo) bit 0..15 => dice del nodo de la derecha (0 si no tiene).
	// (Cigo) bit 0..15
	int treeInsert=1;
	for (i=0;i<=maxCode;i++)
	{
		int len=bits[i];
		if (len!=0)
		{
			code=next_code[len]++;
			// Lo mete en en bol.
			int node=0;
			for (int bit=len-1;bit>=0;bit--)
			{
				int value=code&(1<<bit);
				// Inserta a la izquierda.
				if (value==0)
				{
					int left=aDesData[node]>>16;
					if (left==0)
					{
						aDesData[node]|=(treeInsert<<16);
						node=treeInsert++;
					}
					else node=left;
				}
				// Inserta a la derecha.
				else
				{
					int right=aDesData[node]&0xFFFF;
					if (right==0)
					{
						aDesData[node]|=treeInsert;
						node=treeInsert++;
					}
					else node=right;
				}
			}
			// Inserta el cigo.
			aDesData[node]=0x80000000|i;
		}
	}
	Tools_Free((void**)&bl_count);
	Tools_Free((void**)&next_code);
	return;
}

int GZIP_Len(char* gzip, int aLen)
{
	
	int gzipIndex;
	int gzipByte;
	int gzipBit;
	gzipIndex=gzipByte=gzipBit=0;
	// Cabecera.
	if (readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex)!=0x8B1F||readBits(gzip,8, &gzipBit, &gzipByte, &gzipIndex)!=8)
		return 0;
	// Flag.
	int flg=readBits(gzip,8, &gzipBit, &gzipByte, &gzipIndex);
	// Fecha(4) / XFL(1) / OS(1).
	gzipIndex+=6;
	// Comprueba los flags.
	if ((flg&FEXTRA_MASK)!=0) gzipIndex+=readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex);
	if ((flg&FNAME_MASK)!=0) while (gzip[gzipIndex++]!=0);
	if ((flg&FCOMMENT_MASK)!=0) while (gzip[gzipIndex++]!=0);
	if ((flg&FHCRC_MASK)!=0) gzipIndex+=2;
	// Tama de los datos descomprimidos.
	gzipIndex=aLen-4;
	
	return readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex)|(readBits(gzip,16, &gzipBit, &gzipByte, &gzipIndex)<<16);
}